public class AVLTree {

    static class TreeNode{
        private int val ;
        private int bf ;  // 平衡因子
        private TreeNode left ;
        private TreeNode right ;
        private TreeNode parent ;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    private TreeNode root ;
    public void insert(int val){
         TreeNode node = new TreeNode(val);
        if(this.root == null){
           this.root = node;
        }
        // 找到这个node要放到哪个位置 ;
        TreeNode cur = root ;
        TreeNode parent = null ;
        while(cur != null){
              if(cur.val < val){
                  parent = cur;
                  cur = cur.right;
              }else{
                  parent = cur ;
                  cur = cur.left ;
              }
        }
        // cur为null了,判断 node应该在parent的左边还是右边 ;
        if(parent.val > val){
            parent.left = node;
        }else{
            parent.right = node ;
        }
        cur = node ;
        cur.parent = parent ;

        // 从下往上判断平衡因子 ;
        // 平衡因子为: 右子树-左子树高度
        while (){
            // 判断 cur是左还是右, 右++ , 左--
            if(cur == parent.right){
                parent.bf ++ ;
            }else{
                parent.bf -- ;
            }

            // 判断 parent的bf 是否平衡 ;
            // 等于0 , 表示已经平衡,
            if(parent.bf == 0){
                break;
                // 如果 等于1或等于-1 , 只是这个parent平衡, 继续往上,就会有不平衡的
            }else if(parent.bf == 1 || parent.bf==-1){
                cur = parent ;
                parent = cur.parent ;
            }else{
                // 发现不平衡了, 需要调整
                if(parent.bf ==2 ){      // 右子树 超了 , 要降低右树高度
                    if(cur.bf == 1){


                    }else {

                    }

                }else{                // ==-2 左子树超了 , 要降低左树高度
                    if(cur.bf == 1){


                    }else {    // cur在parent的左边, 要将左子树的节点移到右边, 需要进行右旋



                    }


                }
            }




        }

    }
    //右旋方法
    private void rotateRight(TreeNode root){  // 将要旋转的节点

    }
}
